package 快速排序

// 快速排序
func less(v int, w int) bool {
	return v < w
}

func exch(arr []int, i int, j int) {
	t := arr[i]
	arr[i] = arr[j]
	arr[j] = t
}

func sort(arr []int) {
	lo := 0
	hi := len(arr) - 1
	sortRange(arr, lo, hi)
}

func sortRange(arr []int, lo int, hi int) {
	if hi <= lo {
		return
	}

	p := partition(arr, lo, hi) //返回的是分组的分界值所在的索引, 分界值位置变换后的索引
	sortRange(arr, lo, p-1)     //让左子数组有序
	sortRange(arr, p+1, hi)     //让右子数组有序
}

func partition(arr []int, lo int, hi int) int {
	key := arr[lo]

	//定义两个指针,分别指向待切分元素的最小索引处和最大索引处的下一个位置
	left := lo
	right := hi + 1
	for { //循环
		right--                     //右指针先左移一位
		for less(key, arr[right]) { //先从右向左扫描, 移动right指针, 找到一个比分界值小的元素, 停止
			if right == lo {
				break
			}
		}

		left++                     //左指针向右移一位
		for less(arr[left], key) { //从左向右扫描, 移动left指针, 找到一个比分界值大的元素, 停止
			if left == hi {
				break
			}
		}

		if left >= right { //如果左右边界已经相遇了,返回
			break
		} else {
			exch(arr, left, right)
		}
	}

	exch(arr, lo, right) //将开头0位置元素, 放到对应中间位置

	return right
}
